Batch 3 - Class 196 - Parity III

Pre-Class Exercise

(MartinShCol - 1.6) Take a 3x3 Rubik cube. A termite starts at one of the outer cubes, and goes from one cube to next, never coming back to a cube it has been through, and never going diagonal. Is it possible for the termite to bore through each of 26 outer cubes and finish the trip at the center cube?

Answer: No. Color alternate cubes black and white. Termite alternates between colors on the cube, and hence can not finish at the center square, which is in the 13 color set (not in the 14 color set)

Instructor Note: Tougher problem. Let students work on it. Then give them a hint to think of this as a two color cube with alternate colors.

Attendance Rohan, Siddhant, Aashvi, Anishka, Anshi, Rhea, Liza, Arnab, Vaazisht, Kushagra, Rehaan, Darsh

Class puzzles

Review principles of Parity

Parity means "equal" or "at par" - typically involving separating the possibilities into two parts. Those two parts could be even or odd, black or white, clockwise or anticlockwise, and so on
Thinking of a problem as a parity problem is often non-trivial. Sometimes looking at specific cases, or smaller problems and patterns helps.

(MC Chap 1, Prob 20) Numbers 1 to 10 are written in a row. Can you insert signs + and - so that the value of resulting expression is 0?

Answer: No. Sum is 55, and changing any sign changes the result by even number

(MartinShCol - 12.1) Your king is on a corner cell of a chessboard, and opponent's knight is on the corner cell diagonally opposite. Knight moves first. For how many moves can the king avoid being checked?

Answer: Forever. Move the king towards center and always keep it in opposite color to knight, so that when knight moves it will not be able to check, since knight always changes color on a move. Why is it important to be in center?

Instructor Note: Remind of prior knight problem, and the fact that knight always changes color on the move

(MC Chap1, Prob 16) Can one make change for a 25-rupee note, using in all ten bills each of 1,3, or 5 rupees?

Answer: No. Sum of even number of odd numbers is even

(MCDiaries 1 - Chap 9 - 6) There are 6 guards at six corners of a hexagonal fortress. Every fifteen minutes, two random guards get bored, and they change their position to an adjacent tower, moving either clockwise or anti-clockwise. Can all six guards land up a the same position?

Answer: No. If you color alternate towers black and white, initially you have 3 black and 3 white guards. At each fifteen minutes, two guards change positions, and so the number of white guards (and black guards) changes by 2. So white (or black guards) can never go to zero.

(MCDiaries 1 - Chap 10 - 6) A round necklace contains 45 beads of two different colors: red and blue

Prove that it is possible to find two beads of the same color next to each other
Prove that it is possible to find two beads of the same color separated by exactly two beads

Answer: Take beads separated by two beads, eg 1,4,7,... - given that there are 15 of them, they must have two of the same color

Homework:

(MCDiaries 1 - Chap 9 - 4) Nelli faces two doors, one which has 20 random numbers and another which has 21 random numbers. Nelli must pick one door, and of the random numbers behind that door, erase one number so that the sum of remaining numbers is even. Which door should Nelli pick to be able to always do this successfully?

Answer: 21 door. There could be 20 odd numbers behind the other door. However, on the 21 door, if the sum of all 21 numbers is odd, there must be at least one odd number which can be removed; similarly if the sum is even, then there must be at least one even number which can be removed.

Extra Puzzles:

(MCDiaries 1 - Chap 10 - 8)

Can you draw a quadrilateral and a straight line so that the line crosses every edge of the quadrilateral (without passing through a vertex)?
Can you draw a decagon (10-sided polygon) so that the line crosses every edge of the decagon?
Can you draw a 11-sided polygon so that the line crosses every edge of the decagon?

Answer: No. Two-Color the vertices of the polygon so that vertices on opposite side are colored differently. There will a contradiction on coloring.

(MCDiaries 1 - Chap 10 - 9) Six stacks of coins are placed on the table. The first has 1 coin, the second has 2 coins, and so on the last one has 6 coins. You are allowed to select any two stacks and add one coin to each, any number of times. Can you make the stacks equal?

Answer: No. The number of coins starts with odd and remains odd

There are numbers 1,2,3,.. 1988 written on the board. At any step, you can erase two numbers and replace them by their difference. Is it possible to get to all zeros on the board?

Answer: Yes. Subtract successive terms to get 994 1's and then subtract again
Ok, real puzzle - how about 1,2,3,...1989?

Answer: No. total parity of sum of numbers on the board remains the same in each step. Since we are starting with an odd parity, we can never land up with all 0's.

Each square of a 9 x 9 board has a bug sitting on it. On a signal, each bug crawls onto one of the squares which shares a side with the one the bug was on. (a) Prove that one of the squares is now empty. (b) Can the bugs move so that there would be exactly one empty square?

Answer (a) Color the squares black and white. There will be one more than the other, and one of those colors will be empty, since each bug changes color
Answer (b) All bugs except center square swap. The center squares remains empty

References:

Mathematical Circles (Russian Experience), by Dmitri Fomin, Sergey Genkin, Ilia Itenberg

Mathematical Circle Diaries, Year 1, by Anna Burago

The Colossal Book of Short Puzzles and Problems, by Martin Gardner